package com.leetcode.根据算法进行分类.滑动窗口相关;

/**
 * @author: ZhouBert
 * @date: 2021/2/2
 * @description: 424. 替换后的最长重复字符
 * https://leetcode-cn.com/problems/longest-repeating-character-replacement/
 */
public class B_424_替换后的最长重复字符 {

    public static void main(String[] args) {
        String s = "ABAB";
//		s = "AABABBA";
//		s = "ABBB";
        s = "AAAB";
        int k = 2;
//		k = 1;
//		k = 2;
        k = 0;
        B_424_替换后的最长重复字符 action = new B_424_替换后的最长重复字符();
        int res = action.characterReplacement(s, k);
        System.out.println("res = " + res);
    }

    /**
     * 【滑动窗口】总感觉在某些方面不能立刻理解，决定好好缕一缕。
     * 看了题解以后，得出来的过程：
     * 1.创建两个指针 left,right 分别指向滑动窗口的左右边界；
     * 2.只要得出来窗口的大小，就不会缩小：需要记录窗口中最大的元素，当窗口不满足K的条件时，
     * left++,right++;否则 right++;
     * --
     * 如何以O(1) 的时间复杂度计算出子串是否满足K 的条件是个难点。
     * -- 实际上不需要维护 maxCount，因为只需要最大的计数，是我想得太复杂了。
     * 想考虑到边边角角的问题，于是消耗了自己的精力，却增大了去往目的地的距离。
     * TODO:charAt 会检查数组的下标是否越界！所以应该避免频繁使用
     *
     * @param s
     * @param k
     * @return
     */
    public int characterReplacement(String s, int k) {
        //左闭右开的区间，好处是 size= right - left
        if (s == null) {
            return 0;
        }
        int len = s.length();
        if (len < 2) {
            return len;
        }
        int left = 0;
        int right = 0;
        int maxCount = 0;
        //由于需要频繁使用，所以直接转为数组来用
        char[] chars = s.toCharArray();
        int[] freq = new int[26];
        int res = 0;
        while (right < len) {
            freq[chars[right] - 'A']++;
            maxCount = Math.max(maxCount, freq[chars[right] - 'A']);
            right++;
            if (maxCount + k < right - left) {
                freq[chars[left] - 'A']--;
                left++;
            }

//            res = Math.max(res, right - left);
        }
        return right - left;
    }

    /**
     * 此时只考虑往后的，没有考虑往前的方向。
     * 但是最佳答案可能在于既存在往前又存在往后的方向。
     * 那么就有点麻烦，似乎需要递归来求解，自底向上。
     * 但是再一思考，如果一直定的是往后的方向，那么此时往前的方向必定跟上一个往后的方向重叠，
     * --
     * 虽然是我自己的思路，但是转换为代码上确实不清晰。
     * --
     * 决定好好学习一下【滑动窗口】！
     * 关键点就是我们如何判断一个字符串改变 KK 个字符，能够变成一个连续串
     *
     * @param s
     * @param k
     * @return
     */
    public int characterReplacementFail(String s, int k) {
        int len = s.length();
        int res = 1;
        int begin = 0, end = 1, step = 0, preEnd = end;
        int lastIndex = len - 1;
        //上一个值
        int value = s.charAt(0);
        while (end < len) {
            step = 1;

            if (s.charAt(end) != value) {
                preEnd = end;
                //说明不符合
                while (end < lastIndex && step <= k) {
                    if (s.charAt(++end) != value) {
                        step++;
                    }
                }
                if (end == lastIndex && step <= k) {
                    end++;
                }
                res = Math.max(res, end - begin);
                //... 不只是往后的方向
                if (k >= begin) {
                    //判断到达左边界的情况
                    res = Math.max(res, preEnd - begin + 1);
                }


                begin = preEnd;
                end = begin;
                value = s.charAt(begin);
            } else {
                res = Math.max(res, end - begin + 1);
            }
            preEnd = end++;
        }
        if (k >= begin) {
            //判断到达左边界的情况
            res = Math.max(res, preEnd - begin + 1);
        }

        return res;

    }


}
